Today, online content is often closely associated with online advertisements. Thus, websites or web applications and the like that deliver content to users can also act as advertisement hosts for advertisers. That is, while a user receives certain content, that user can simultaneously be exposed to relevant ads. For example, Internet search engines can sell ad slots to advertisers based upon the search string entered by an end user or the search results. In another example, webmail providers can parse text from emails in order to determine an appropriate category for an advertisement, and once determined, display an ad from an advertiser in that category. Of course many further examples exist.
As can be appreciated, potential advertisement space (e.g., ad slots) can arise in a very dynamic and sudden fashion. For example, the particular keywords that an end-user enters into a search engine, the actual text of an email that is sent or received by a user, etc. cannot be known in advance, even if predictive algorithms, empirical data and the like can provide for estimates. Accordingly, it is not clear a priori how many ad slots for any given ad category will be available to advertisers for purchase.
Moreover, while advertisers may have designated a budget to spend on ad slots, it is presumed to be in their best interest to go over that budget should the ad slots be available. That is, even though each addition ad slot will cost the advertiser money beyond the designated budget, the additional ads will translate into additional clicks, which will in turn equate to more revenue-generating transactions. Hence it is in the interest of advertisers to purchase available ad slots and also in the interest of the ad host to sell all available ad slots, even though number and/or category of ads cannot be known in advance and the actual allocation of such can present various difficulties.
Accordingly, generalized online matching was recently introduced in a paper by A. Mehta, et. al., entitled, “Adwords and Generalized Online Matching” in the context of Ad-Auctions. The disclosure provides two algorithms, both very simple, with competitive ratio 1−1/e (e.g., 63.2%) under the assumption that the maximum bid is negligible compare to the minimum budget. However, the proof of both algorithms is very complicated, long, and, as termed by the authors themselves, “counter-intuitive”. Moreover, the proof supplied for the algorithms is provided in stages and introduce one additional complication of the problem in each stage. In addition, there is evidence that the algorithms themselves are not optimal and do not lend themselves to additional flexibility such as application to other aspects of the Ad-Auction universe.